Data to be stored for later retrieval are typically stored in encoded form. Prior to their storage, the data symbols are encoded using an error correction code (ECC). Encoding the data avoids the loss of information through misinterpretation of the retrieved data, should one or more of the data symbols become corrupted due, for example, to a defect in the recording medium, such as a disk, or to noise signals in associated read or write channels. The result of misinterpreting the retrieved data symbols is erroneous data, and the error correction code is employed to, as the name implies, correct the erroneous data.
Specifically, before a string of data symbols is recorded, it is mathematically encoded to form ECC symbols. The ECC symbols are then appended to the data string to form data code words--data symbols plus ECC symbols--and the data code words are written to, or stored on, the disk after appropriate encoding with a modulation code. As recording densities increase, "N" code words are typically interleaved before they are recorded in a sector. When data are read from the disk, the interleaved code words are retrieved and mathematically decoded. During decoding, errors in the data are detected and, if possible, corrected through manipulation of the associated ECC symbols [For a detailed description of decoding see Peterson and Weldon, Error Correction Codes, 2d Edition, MIT Press, 1972].
When the data recorded in a sector are retrieved from storage, they are manipulated in a conventional manner to de-interleave the N code words and determine the locations of errors and the associated error values. The system then corrects the errors by combining the error values with the associated erroneous bits or symbols.
There are essentially two ways to classify errors--as random errors or as burst errors. A random error is an independent error that occurs in a code word symbol. A burst error is a sequence of contiguous bits or symbols in which at least the first bit or symbol and the last bit or symbol are erroneous, and the bits or symbols between the first and last may but need not be erroneous. Burst errors result from, for example, a storage medium defect that adversely affects a portion of a sector, and thus, affects a number of the interleaved code words. As data are stored more densely, defects in the storage medium tend to involve more and more bits, and thus, produce more and more burst errors.
Systems are more often using maximum likelihood demodulators to demodulate the retrieved data. These demodulators tend to correct random errors in the retrieved data by selecting "legitimate" sequences of bits, based on a sequence of retrieved bits that may contain one or more erroneous bits. The demodulator uses information about the modulation code to select, as the most likely recorded bits, a sequence of bits that is closest to the retrieved bits and meets the constraints of the modulation code.
The maximum likelihood demodulators may actually introduce bursty errors into the demodulation, by selecting as most likely the wrong sequence of bits. The demodulator is more apt to make such a selection if the retrieved data are corrupted.
The sequences selected by the maximum likelihood demodulator are legitimate sequences of bits, even if they are the wrong sequences, that is, even if they are not the sequences that were recorded. These sequences are then de-interleaved and decoded to reproduce the N code words.
If the retrieved data contains too many errors the data may be mistakenly demodulated, and then interpreted as different (but legitimate) code words. This is the worst type of decoding mistake, since the system "corrects" these code words, as necessary, using the ECC, and then treats the data symbols as error-free. Accordingly, as recording density increases, it is becoming more and more important to count the number of burst errors in the N retrieved code words, so that this decoding problem can be avoided by limiting error correction to those sectors that contain a relatively small number of burst errors.
A burst error occurs as a number of bits or symbols. Since all the bits or symbols in a burst need not be erroneous, there is an ambiguity in determining the start and length of each burst. There is thus a problem in determining if a retrieved sector of data contains a number of burst errors that exceeds the predetermined error correcting limit.
To count the number of burst errors in the retrieved data, the system examines the error pattern for the entire sector of data. The error pattern is determined from the error locations and the error values for the N code words. These are provided by the ECC during decoding. A zero in the pattern represents a correct bit and a one in the pattern represents an erroneous bit. The pattern includes the same number of bits as those recorded the sector.
Consider an error pattern:
______________________________________ 00100011000000000010100000000000011100000 . . . ______________________________________
The number of burst errors in this segment of the pattern can be counted as:
eight 1-bit bursts; PA1 three 1-bit bursts, one 2-bit burst and one 3-bit burst; PA1 one 1-bit burst, one 2-bit burst and two 3-bit bursts; PA1 one 6-bit burst, and two 3-bit bursts; and so forth.
There is thus a need for a system to determine, for an error pattern, a unique number of burst errors. Once the number of error bursts is known, such a system can restrict, or limit, its error correcting to sectors that contain up to or less than the number of burst errors that are encountered during normal operations of the system.